import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Solution946 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int cur=0;
        Stack<Integer> stack=new Stack<>();
        Set<Integer> set=new HashSet<>();
        for (int i=0;i<popped.length;i++){
            if (!set.contains(popped[i])){
                while (pushed[cur]!=popped[i]){
                    stack.push(pushed[cur]);
                    set.add(pushed[cur]);
                    cur++;
                }
                stack.push(pushed[cur]);
                cur++;
            }
            if (stack.pop()!=popped[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution946().validateStackSequences(new int[]{1,2,3,4,5},new int[]{4,5,3,2,1}));
    }
}
